package _21_bestTimeToBuyAndSellStock

import (
	"fmt"
	"math"
)

/**
Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

*/

func main() {
	fmt.Println(maxProfit([]int{7, 1, 5, 3, 6, 4}))
}

/**
观察法

盈利=卖出价-买入价

第i个位置之前最低价格为min
第i个位置的收益等于price(i)-min
遍历一次即可

该方法最快

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}

	profit := 0
	min := prices[0]
	for i := 1; i < len(prices); i++ {
		if min > prices[i] {
			min = prices[i]
		}

		if profit < prices[i]-min {
			profit = prices[i] - min
		}
	}

	return profit
}
*/
/**
dp实现

opt(n)是第n天的最大收益，按在不在第n天卖出分为a,b两种情况
a是不在第n天卖出的最大收益 opt(n-1)
b是在第n天卖出的最大收益 第n天价格-前n-1天最低价格

opt(n)等于max(a,b)

*/

/*
func maxProfit(prices []int) int {
    if len(prices)<=1{
        return 0
    }

    opt:=make([]int,len(prices))
    opt[0] = 0

    for i:=1;i<len(prices);i++{
        a:=opt[i-1]
        b:=prices[i]-min(prices[:i])
        opt[i] = int(math.Max(float64(a),float64(b)))
    }

    return opt[len(prices)-1]
}
*/

/**
递归实现

位置	0  1  2  3  4  5
值	7, 1, 5, 3, 6, 4
*/

func maxProfit(prices []int) int {
	if len(prices) <= 1 {
		return 0
	}

	a := prices[len(prices)-1] - min(prices[:len(prices)-1])
	b := maxProfit(prices[:len(prices)-1])

	return int(math.Max(float64(a), float64(b)))
}

func max(a []int) int {
	m := a[0]
	for i := 1; i < len(a); i++ {
		if m < a[i] {
			m = a[i]
		}
	}
	return m
}

func min(a []int) int {
	m := a[0]
	for i := 1; i < len(a); i++ {
		if m > a[i] {
			m = a[i]
		}
	}
	return m
}
